package com.graph;

import lombok.Getter;

import java.util.*;

/**
 * @Author: tgy
 * @Date: 2020-10-28 16:03
 */
@Getter
public class AdjacencyListGraph01<V,E> extends AbstractGraph<V,E> {

    /**
     * value 相等就是同一个节点
     * @param <V>
     * @param <E>
     */
    private static class Vertex<V,E> {

        V value;
        Set<Edge<V,E>> outEdges;
        Set<Edge<V,E>> inEdges;

        public Vertex(V value) {

            this.value = value;
            outEdges = new HashSet<>();
            inEdges = new HashSet<>();
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (!(o instanceof Vertex)) {
                return false;
            }

            Vertex<?, ?> vertex = (Vertex<?, ?>) o;

            return value != null ? value.equals(vertex.value) : vertex.value == null;
        }

        @Override
        public int hashCode() {
            return value != null ? value.hashCode() : 0;
        }

        @Override
        public String toString() {
            return "{" + value +
                    ", outEdges=" + outEdges +
                    ", inEdges=" + inEdges +
                    '}';
        }
    }

    /**
     * from ，to 节点相等就是相同的边
     * @param <V>
     * @param <E>
     */
    private static class Edge<V,E> {

        Vertex<V,E> from;
        Vertex<V,E> to;

        E weight;

        public Edge(Vertex<V, E> from,E weight, Vertex<V, E> to) {
            this.from = from;
            this.weight = weight;
            this.to = to;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (!(o instanceof Edge)) {
                return false;
            }

            Edge<?, ?> edge = (Edge<?, ?>) o;

            if (from != null ? !from.equals(edge.from) : edge.from != null) {
                return false;
            }
            return to != null ? to.equals(edge.to) : edge.to == null;
        }

        @Override
        public int hashCode() {

            int result = from != null ? from.hashCode() : 0;
            result = 31 * result + (to != null ? to.hashCode() : 0);
            return result;
        }

        @Override
        public String toString() {
            return "{" +
                    "from=" + from.value +
                    ", to=" + to.value +
                    ", weight=" + weight +
                    '}';
        }
    }

    private int edgeCount;

    private HashMap<V,Vertex<V,E>> vertices;

    public AdjacencyListGraph01(Operations<E> operations) {
        super(operations);
        vertices = new HashMap<>();
    }

    public AdjacencyListGraph01() {
        this(null);
    }

    @Override
    public int verticesSize() {

        return vertices.size();
    }

    @Override
    public int edgesSize() {

        return edgeCount;
    }

    @Override
    public void addVertex(V v) {

        Vertex<V, E> vertex = vertices.get(v);

        if (Objects.nonNull(vertex)) {

            return;
        }

        vertices.put(v,new Vertex<>(v));
    }

    @Override
    public void addEdge(V from, V to) {

        this.addEdge(from,to,null);
    }

    @Override
    public void addEdge(V from, V to, E weight) {

        Vertex<V, E> fromVertex = vertices.get(from);

        if (Objects.isNull(fromVertex)) {

            fromVertex = new Vertex<>(from);
            vertices.put(from,fromVertex);
        }

        Vertex<V, E> toVertex = vertices.get(to);

        if (Objects.isNull(toVertex)) {

            toVertex = new Vertex<>(to);
            vertices.put(to,toVertex);
        }


        Edge<V, E> newEdge = new Edge<>(fromVertex, weight, toVertex);

        if (fromVertex.outEdges.remove(newEdge)) {

            toVertex.inEdges.remove(newEdge);
        }

        fromVertex.outEdges.add(newEdge);
        toVertex.inEdges.add(newEdge);
        edgeCount++;
    }

    @Override
    public void removeVertex(V v) {

        Vertex<V, E> vertex = vertices.get(v);

        if (Objects.isNull(vertex)) {

            return;
        }

        for (Edge<V, E> outEdge : vertex.outEdges) {

            outEdge.to.inEdges.remove(outEdge);
            edgeCount--;
        }

        for (Edge<V, E> inEdge : vertex.inEdges) {

            inEdge.from.outEdges.remove(inEdge);
            edgeCount--;
        }

        vertices.remove(v);

    }

    @Override
    public void removeEdge(V from, V to) {

        Vertex<V, E> fromVertex = vertices.get(from);
        Vertex<V, E> toVertex = vertices.get(to);
        if (Objects.isNull(fromVertex) || Objects.isNull(toVertex)) {

            return;
        }

        Edge<V, E> edge = new Edge<>(fromVertex, null, toVertex);

        if (fromVertex.outEdges.remove(edge)) {

            toVertex.inEdges.remove(edge);
            edgeCount--;
        }

    }

    @Override
    public void bfs(V v, Traversal<V> traversal) {

        Vertex<V, E> vertex = vertices.get(v);

        if (Objects.isNull(vertex) || Objects.isNull(traversal)) {

            return;
        }

        Queue<Vertex<V, E>> queue = new LinkedList<>();
        HashSet<Vertex<V, E>> visitors = new HashSet<>();
        queue.offer(vertex);
        visitors.add(vertex);

        while (!queue.isEmpty()) {

            vertex = queue.poll();

            if (traversal.visitor(vertex.value)) {

                return;
            }

            for (Edge<V, E> outEdge : vertex.outEdges) {

                if (visitors.contains(outEdge.to)) {
                    continue;
                }
                queue.offer(outEdge.to);
                visitors.add(outEdge.to);
            }
        }

    }

    @Override
    public void dfs(V v, Traversal<V> traversal) {

        Vertex<V, E> vertex = vertices.get(v);

        if (Objects.isNull(vertex) || Objects.isNull(traversal)) {

            return;
        }

        Stack<Vertex<V, E>> stack = new Stack<>();
        HashSet<Vertex<V, E>> visitors = new HashSet<>();

//        // 加进去的都是要访问的
//        stack.push(vertex);
//        visitors.add(vertex);
//
//        while (!stack.empty()) {
//
//            vertex = stack.pop();
//
//            if (traversal.visitor(vertex.value)) {
//
//                return;
//            }
//
//            for (Edge<V, E> outEdge : vertex.outEdges) {
//
//                Vertex<V, E> toVertex = outEdge.to;
//                if (visitors.contains(toVertex)) {
//                    continue;
//                }
//
//                stack.push(toVertex);
//                visitors.add(toVertex);
//            }
//        }

        stack.push(vertex);
        visitors.add(vertex);

        if (traversal.visitor(vertex.value)) {

            return;
        }

        while (!stack.empty()) {

            vertex = stack.pop();

            for (Edge<V, E> outEdge : vertex.outEdges) {

                if (visitors.contains(outEdge.to)) {

                    continue;
                }


                stack.push(outEdge.from);
                stack.push(outEdge.to);

                if (traversal.visitor(outEdge.to.value)) {

                    return;
                }

                visitors.add(outEdge.to);
                break;
            }

        }

    }


    @Override
    public List<V> topologicalsort() {
        return null;
    }

    @Override
    public Set<EdgeInfo<V, E>> minimumSpanningTree() {
        return null;
    }


    @Override
    public Map<V, PathInfos<V, E>> shortestPath(V v) {
        return null;
    }

    @Override
    public Map<V, Map<V, PathInfos<V, E>>> allShortestPath() {
        return null;
    }

    @Override
    public Map<V, ShortestPath<V, E>> customShortestPath(V v) {
        return null;
    }


    @Override
    public String toString() {

        StringBuilder sb = new StringBuilder();

        sb.append("边条数:").append(edgeCount).append("\n");
        for (Map.Entry<V, Vertex<V, E>> entry : vertices.entrySet()) {

            sb.append(entry.getValue()).append("\n");
        }

        return sb.toString();
    }
}
